1. Field of Invention
This invention relates to the display of information. The invention is further related to the display of detailed addressing or location information of objects placed on a map, chart, graph or other display types. The invention is more particularly related to the display of zip code, proximity, or radius data for locations not precisely identified on a map. The invention is also related to geocoding point data as line information in a single layer geocoded database. The invention is still further related to the display of geocoded point data as one or more lines (radials) emanating from a centroid formed from an endpoint placed in a predetermined direction from the centroid.
2. Discussion of Background
Maps and methods of displaying information are utilized in many devices. Maps, for finding locations of cities, houses, or other destinations generally display routes and points or shaded areas designating populated areas, cities, states, parks, points of interest, etc. Additional information about cities or roads may be printed on the map in close proximity to the designation (Cleveland, pop. 2,300,000, for example). Such information may also be printed as an index at a bottom or reverse side of the map (an index of streets or cities, along with a grid identifier, G-3, for example).
Some Internet applications using mapping data (directed graphs, for example) have been adapted for display of any of selected areas or for finding address locations and driving directions. For example, on-line maps and driving directions are available at mapsonus.com. Mapsonus provides on-line users with an opportunity to input an address and retrieve an electronic map displayed on their screen.
Methods of displaying information include driving maps (like mapsonus) and various tracking devices, including satellite tracking. Satellite tracking software is available over the Internet and includes examples such as WinTrak at hsv.tis.net/˜wintrak/. Satellite tracking programs typically utilize an input file having orbital elements describing an orbit of a satellite and output a spherical display or flat map of the earth along with a track (route) of the satellite(s) described by the orbital elements. Other information about the satellites are typically printed at a bottom area of the satellite tracking display, shown in a pop-up window, or accessed via another screen (activated by a control key sequence or a pull down menu, for example).
Additional information on traditional maps is typically available, but fixed (not updatable without purchasing a new map), and often buried in tables or other indexes not necessarily linked to any of the items they describe. Internet based maps and other computer program or Internet displays (satellite tracking software, for example) are typically too crammed with general area and background information (e.g., routes, paths, street names, etc.) to display additional information on the maps themselves.
Electronic or software based maps are typically based on mapping information stored in a database. The maps themselves are not stored, but information to create the maps is stored in a computer readable format, typically a directed graph. A directed graph stores nodes and edges connected into a graph that is utilized for route searching and planning. A more complete description of directed graphs can be found in Suranyi, U.S. Pat. No. 6,885,937 entitled “SHORTCUT GENERATOR.” issued Apr. 26, 2005, incorporated herein by reference, in its entirety. Directed graphs are useful for determining routing and cost information for travel between points in the graph.
Geocoding, also known as location coding, assigns a position (usually latitude and longitude coordinates) to street addresses. Auxiliary information, such as the precision and source of the latitude and longitude coordinates may also be included in the geocoded information.
Generally, the geocoded information (addresses, latitude/longitude (lat/long) for that address, and additional precision information is maintained in a database. Typically a geocoded database includes lat/long information for street segments or lines maintained in the database. Address information is searched against the database to find a corresponding street segment. Based on an address range of the corresponding street segment, a position of the address is determined (for example, a street segment having an address range of 101-200, is correlated to an address of 176, which has a position of 76% of the distance from 101 to 200 in the segment). Lat/long is interpolated based on the position of the address with respect to record information maintained about the corresponding street segment. Table 1 provides an example of one possible result of a search of five addresses against a geocoded database.
TABLE 1Search CriteriaSearch ResultsStreetNo.NameCty/StateLatLongPost100CornerSan Fran,117.52 W38.621 NStreetMarketCAPost876LouieSan Fran,117.53 W38.621 NStreetMarketCAAlbertly356PolandParma, OH105.17 W42.522 NAvePark Ave1200Apart-New York103.44 W43.198 NmentCity, NYMiramar3600MalibuSan116.54 W37.233 NRdRaceTkDiego, CA
As can be seen by Table 1, the geocoded database search returns location information (lat/long coordinates) matched to address, name, and city/state. The geocoding process itself is the placement (or linking) of the addressing or other info in the database in correlation with a location (lat/long). This linking may be done in a database which stores one lat/long or location for each address. However, it is more efficient to link address to locations (lat/long) by interpolating the address position based on a known location (location of a segment for example) as discussed in the above example.
Searching a geocoded database for matches commonly involves use of two or more distinct data layers in order to get a high match rate. Typically, a first layer consists of lines or streets. Second and additional layers are typically composed of centroids that represent a common feature of a larger area. Often centroids will represent a set of address ranges, perhaps matching different data source types (zip codes, or population centers, for example). When locations, addresses, or other points are not precisely located on a map or graph (i.e., not found in a search of the first layer—lines or streets), they are then searched against the second or subsequent layers and matched against a centroid that matches a broader characterization of the point being searched. For example, when a specific address is not found in the lines and streets of layer 1, a zip code of the address is matched against zip code centroids of layer 2. If a zip centroid matches the address, a location of the matching zip centroid is returned as a match.
However, several problems arise with searches of geocoded databases. First, a program searching the database is required to access and use multiple data layers. The data layers are separately maintained and a pass on each data layer is needed for all data to be considered in the search. After a first pass, any records that fail to make a match are passed on and searched against the next data layer and so on. Combining tasks in an automated fashion, requires additional computational tasks, is slower, making interactive geocoding more difficult.
Another problem associated with prior geocoding techniques is that multiple geocode matches to a same geographic centroid location, even if the matches are of different source types or different types of information are anchored to a same location (a default address, population center, or zip code centroid, for example). Because the centroid is a point in the database, each match collapses onto the same location (each match having a same zip code, for example).
Referring to FIG. 1, there is illustrated one example of a map 100 that has been geocoded with street addresses 1-8 110, correlating a location on the map to known street addresses, and using a centroid 140 for identification of unregistered or unknown address locations. Locations 1 and 2 (representing 112 and 182 Main St., respectively) are shown at their respective geocoded locations on Main St. 120. Location 4 (representing 254 1st St.) is shown at its geocoded location on 1st St. 130. However, addresses 3, and 5-8 corresponding to Rhubarb St., Flower St., 19th Ave., and Blossom Dr. do not have exact geocoded locations and are placed at the centroid 140. Identification of matches for addresses 3, and 5-8 all collapse onto the centroid 140 and fail to provide any additional information about the addresses.
Another example is shown in FIGS. 2A and 2B. In FIG. 2A, a mapquest query is performed on 852 Nothere St., identified in the query as part of San Francisco, Calif., 94111. Since 852 Nothere St. was not found in the mapquest database, an identifier 210 was placed on a map 200 of San Francisco's 94111 zip code (at a zip code based centroid or other anchor point of the 94111 zip code). In FIG. 2B, a mapquest query on 852 SamePlace Ave., also identified in the query as part of San Francisco, Calif., 94111. Since 852 SamePlace Ave. was not found in the mapquest database, an identifier 220 was placed at a same location on the map 200 as identifier 210 (at a same zip code based centroid or anchor point of the 94111 zip code). FIG. 2C provides a comparison of an exact match 230 made on an address found in the mapquest database. Additional information about the matches is not displayed on the map 200, but some additional information is shown in the query box 250 and info bar 260.